package com.chixing.day03;

/**
 * 该类包含了数组常见的排序方式
 */
public class SortUtil {
    //冒泡排序:相邻元素比较顺序
    public static void bubboSort(int[]a){
        for (int i=0;i<a.length-1;i++){
            for (int j=0;j< a.length-i-1;j++){
                if (a[j]>a[j+1]){
                    int temp=a[j];
                    a[j]=a[j+10];
                    a[j+1]=temp;
                }
            }
        }
    }
    //选择排序
    public static void selectSort(int[]a) {
        for ( int i = 0; i < a.length-1; i++) {
            for (int n = i+1; n < a.length ;n++) {
                if (a[i] > a[n]) {
                    int temp = a[i];
                    a[i] = a[n];
                    a[n] = temp;
                }
            }
        }
    }
    //快速排序
    //67，23，12，91，56，16，88，99，
    /*
        16，23，12，91，56，[16]，88，99
        16，23，12，[91]，56，91，88，99
     */
    // 一趟内部的排序
    public static int getMiddle(int[]a,int low,int high){//low=2,high=5
        int p =a[low];//67
        while (low<high){
            while (low<high&&p<a[high]){
                high--;
            }
            a[low]=a[high];
            while (low<high&&p>=a[low]){
                low++;
            }
            a[high]=a[low];
        }
        //low==high
        a[low]=p;
        return low;
    }
    public static void quickSort(int[]a,int low,int high){
        int middle=getMiddle(a,0, a.length-1);

        if (low<high){
            quickSort(a,low,middle-1);//左边
            quickSort(a,middle+1,high);//右边
        }
    }
}
